package com.demo.java.OD301_350.OD343;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【聚餐地点 or 欢乐的周末(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146159133
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取地图的尺寸
        int x = sc.nextInt();
        int y = sc.nextInt();

        // 初始化地图
        int[][] maze = new int[x][y];
        List<int[]> startPoints = new ArrayList<>(); // 起始点列表
        List<int[]> goalPoints = new ArrayList<>(); // 目标点列表

        // 读取地图数据
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                maze[i][j] = sc.nextInt();
                if (maze[i][j] == 2) {
                    startPoints.add(new int[]{i, j}); // 第一个起始点
                } else if (maze[i][j] == 3) {
                    goalPoints.add(new int[]{i, j}); // 目标点
                }
            }
        }

        // 定义四个方向的移动
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // 分别对两个起始点进行BFS
        boolean[][] reachableFromStart1 = bfs(maze, startPoints.get(0), directions, x, y);
        boolean[][] reachableFromStart2 = bfs(maze, startPoints.get(1), directions, x, y);

        // 统计两个起始点都能到达的目标点数量
        int result = 0;
        for (int[] goal : goalPoints) {
            int gx = goal[0], gy = goal[1];
            if (reachableFromStart1[gx][gy] && reachableFromStart2[gx][gy]) {
                result++;
            }
        }

        // 输出结果
        System.out.println(result);
    }

    // BFS算法，用于从起始点进行搜索，返回每个点是否可达的布尔矩阵
    public static boolean[][] bfs(int[][] maze, int[] start, int[][] directions, int x, int y) {
        boolean[][] visited = new boolean[x][y];
        Queue<int[]> queue = new LinkedList<>();
        int startX = start[0], startY = start[1];

        visited[startX][startY] = true;
        queue.offer(start);

        // 广度优先搜索
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int curX = current[0], curY = current[1];

            // 遍历四个方向
            for (int[] direction : directions) {
                int newX = curX + direction[0];
                int newY = curY + direction[1];

                if (isValid(newX, newY, x, y, maze, visited)) {
                    visited[newX][newY] = true;
                    queue.offer(new int[]{newX, newY});
                }
            }
        }

        return visited;
    }

    // 判断当前坐标是否有效
    public static boolean isValid(int x, int y, int maxX, int maxY, int[][] maze, boolean[][] visited) {
        return x >= 0 && x < maxX && y >= 0 && y < maxY && maze[x][y] != 1 && !visited[x][y];
    }
}